class Solution {
    vector<vector<string>> res;
    vector<string> path;
public:
  // 类似回溯组合问题
    bool IsPaliandrome(string& s){
        string tmp = s;
        reverse(tmp.begin(), tmp.end());
        return tmp == s;
    }
    void backtrack(const string& s, int start){
        if(start >= s.size()){
            res.push_back(path);
            return ;
        }
        for(int i = start; i < s.size(); ++i){
            string temp = s.substr(start, i-start+1);
            if(IsPaliandrome(temp)){
                path.push_back(temp);
            }else continue;
            backtrack(s, i+1);  // 继续查找分割后的位置
            path.pop_back();  // 回溯
        }
    }
    vector<vector<string>> partition(string s) {
        res.clear();
        path.clear();
        backtrack(s, 0);
        return res;
    }
};